package LeetCode;


/**
 * @Author: Dijah
 * @Date: 2023/4/7 13:11
 * @Desc: 接雨水
 */
public class code42_trap {

    //使用双指针的方式
    public static int trap(int[] height){
        int n = height.length;
        if(n == 0){
            return 0;
        }
        int left = 0;
        int right = n - 1;
        //左最大
        int l_max = 0;
        //右最大
        int r_max = 0;
        int res = 0;
        while (left < right){
            l_max = Math.max(l_max,height[left]);
            r_max = Math.max(r_max,height[right]);

            if(l_max < r_max){
                res += l_max - height[left];
                left++;
            }else{
                res += r_max -height[right];
                right--;
            }
        }
        return res;
    }


    public static int trap1(int[] height){
        int n = height.length;
        if(n == 0){
            return 0;
        }
        int [] l_max = new int[n];
        int [] r_max = new int[n];
        //初始化l_max,r_max
        l_max[0] = height[0];
        r_max[n - 1] = height[n - 1];
        int res = 0;
        //从左往右依次最大的
        for(int i = 1 ; i < n; i++){
            l_max[i] = Math.max(height[i],l_max[i - 1]);
        }
        //从右往左依次最大的
        for (int i = n - 2; i >= 0; i--){
            r_max[i] = Math.max(height[i],r_max[i + 1]);
        }
        //计算结果
        for(int i = 0 ; i < n; i++){
            res += Math.min(l_max[i],r_max[i]) - height[i];
        }
        return res;
    }

    public static int trap2(int [] height){
        if(height == null || height.length < 2){
            return 0;
        }
        int N = height.length;
        int left = 1;
        int right = N - 2;
        int leftMax = height[0];
        int rightMax = height[N - 1];
        int water = 0;
        //判断索引的位置，两个指针没有相遇，那么就一直循环
        while (left <= right){
            if(leftMax <= rightMax){
                //leftMax的值和height[left]位置的值作比较
                water += Math.max(0,leftMax - height[left]);
                leftMax = Math.max(leftMax,height[left++]);
            }else{
                water += Math.max(0,rightMax - height[right]);
                rightMax = Math.max(rightMax,height[right--]);
            }
        }
        return water    ;
    }

    public static void main(String[] args) {
        int [] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        int i = trap2(height);
        System.out.println(i);
    }
}
